package main

import (
	"container/list"
	"fmt"
)

type LRUCache struct {
	capacity int
	l        *list.List
	m        map[int]*list.Element
}

type Node struct {
	key   int
	value int
}

func Constructor(capacity int) LRUCache {
	return LRUCache{
		capacity: capacity,
		m:        make(map[int]*list.Element),
		l:        list.New(),
	}
}

func (c *LRUCache) Get(key int) int {
	if v, ok := c.m[key]; ok {
		c.l.MoveToFront(v)
		return v.Value.(Node).value
	}
	return -1
}

func (c *LRUCache) Put(key int, value int) {
	if v, ok := c.m[key]; ok {
		c.l.MoveToFront(v)
		v.Value = Node{
			key:   key,
			value: value,
		}
		return
	}

	if c.capacity == len(c.m) {
		last := c.l.Back()
		lastKey := last.Value.(Node).key
		c.l.Remove(last)
		delete(c.m, lastKey)
		c.capacity--
	}

	element := c.l.PushFront(Node{
		key:   key,
		value: value,
	})
	c.m[key] = element
	c.capacity++
	return
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * obj := Constructor(capacity);
 * param_1 := obj.Get(key);
 * obj.Put(key,value);
 */

func main() {
	cache := Constructor(2)
	cache.Put(1, 1)
	cache.Put(2, 2)
	cache.Get(1)
	cache.Put(3, 3)
	v := cache.Get(2)
	fmt.Println(v)

	cache.Put(4, 4)
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * obj := Constructor(capacity);
 * param_1 := obj.Get(key);
 * obj.Put(key,value);
 */
